package mo.leetcode_top;

import java.util.Arrays;
import java.util.List;

public class L315 {

    public List<Integer> countSmaller(int[] nums) {
        Integer[] res = new Integer[nums.length];
        Arrays.fill(res, 0);
        TreeNode root = null;
        for (int i = nums.length-1; i >= 0; i--) {
            root = addAndCount(root, new TreeNode(nums[i]), res, i);
        }
        return Arrays.asList(res);
    }

    private TreeNode addAndCount(TreeNode root, TreeNode node, Integer[] res, int i) {
        if (root == null) {
            return node;
        }
        if (root.val >= node.val) {
            root.count++;
            root.left = addAndCount(root.left, node, res, i);
        } else {
            res[i] += 1 + root.count;
            root.right = addAndCount(root.right, node, res, i);
        }
        return root;
    }

    private static class TreeNode {
        private int val;
        private int count;
        private TreeNode left;
        private TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public static void main(String[] args) {
        L315 test = new L315();
        System.out.println(test.countSmaller(new int[]{5,2,6,1}));
    }
}
